// @algorithm @lc id=1000307 lang=cpp
// @title 6eUYwP

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // @test([10,5,-3,3,2,null,11,3,-2,null,1],8)=3
public:
    // DFS深度优先搜索
    // 主函数
    int pathSum(TreeNode *root, int targetSum) {
        return root ? pathSumStartWithRoot(root, targetSum) + pathSum(root->left, targetSum) +
                          pathSum(root->right, targetSum)
                    : 0;
    }

    // 辅函数
    int pathSumStartWithRoot(TreeNode *root, long long targetSum) {
        if (!root) {
            return 0;
        }
        int count = root->val == targetSum ? 1 : 0;
        count += pathSumStartWithRoot(root->left, targetSum - root->val);
        count += pathSumStartWithRoot(root->right, targetSum - root->val);
        return count;
    }
};